#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;
/*HJJ QQ479287006
 *给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。
 输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */


//按照我的意思这个题用 回溯
vector<int> temp;

void pathSumDfs(TreeNode *root, int target, vector<vector<int>> &ret, int sum) {
    if (!root)
        return;


    temp.push_back(root->val);
    if (sum + root->val == target && !root->left && !root->right)
        ret.push_back(temp);//注意这里是ret 添加了否则.....看offer68吧


    pathSumDfs(root->left, target, ret, sum + root->val);
    pathSumDfs(root->right, target, ret, sum + root->val);

    temp.pop_back();//我擦我凭感觉这里要pop  如果不行的话挨个 pop到初试环境 跟那个回溯三板斧一样了


}

vector<vector<int>> pathSum(TreeNode *root, int target) {
    vector<vector<int>> ret;


    pathSumDfs(root, target, ret, 0);
    return ret;

}